package com.cqs.leetcode.string;

import com.google.common.collect.Lists;

import java.util.List;


/**
 * lixw
 * 2023/3/24
 **/
public class StreamChecker {

    private  final char[] stream = new char[40000];
    private int len = 0;
    private final Node root = new Node();

    class Node {
        private final Node[] next;
        private boolean isLeaf = false;
        public Node() {
            this.next = new Node[26];
        }
    }


    public StreamChecker(String[] words) {
        //构建树
        for (String s : words) {
            Node pre = root;
            for (int i = s.length()-1; i >= 0; --i) {
                char c = s.charAt(i);
                int idx = c - 'a';
                if (pre.next[idx] == null) {
                    pre.next[idx] = new Node();
                }
                pre = pre.next[idx];
            }
            pre.isLeaf = true;
        }
    }


    public boolean query(char letter) {
        stream[len++] = letter;
        //查询数
        Node node = root;
        for (int i = len - 1; i >= 0; i--) {
            char c = stream[i];
            node = node.next[c - 'a'];
            if (node == null) {
                return false;
            }
            if (node.isLeaf) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        List<String> querys = Lists.newArrayList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l");
        String[] strs = new String[]{"cd", "f", "kl"};
        StreamChecker checker = new StreamChecker(strs);

        querys.forEach(s -> System.out.println(checker.query(s.charAt(0))));

    }
}
